`Arc` instead of `Vec`

A potentially hot take, according to the author.

The use case here is when you have:

• immutable data
• especially when data is to be used as part of something bigger (struct fields, arrays or collections)
• that implements Clone.¹

Why?

1. Arc<[T]> is a much more memory efficient version of Vec<T>. Each element in the former uses 16 bytes vs 24 bytes.²
2. Cloning is extremely cheap, and also in constant time!! O(1)
3. Arc<[T]> like Vec<T> implements Deref<[T]> which means it’s ergonomically the same to use.
4. Proper use of API, since Vec fundamentally implies that the variable can be mutable.

Vec<str> vs String

Are equivalent

Memory layout of Vec

Three parts to it, each taking 8 bytes

• Pointer to underlying data on the heap
• Length of the underlying data
• Capacity of the underlying data

On .clone, a deepcopy of the underlying data occurs. This is slow as it requires expensive allocation of memory, and is linear to the size of the data O(n). Worth noting that cloning create a copy of the underlying heap data, with no extra capacity (capacity == len).

Memory layout of Arc

When data is put into Arc, the underlying data lies on the heap with three parts

• Strong reference count (8 bytes)
• Weak reference count (8 bytes)
• Underlying data itself

When a variable takes an immutable reference of an Arc, the reference only has two parts:

• Pointer (8 bytes)
• Length (8 bytes)

On .clone, a new struct reference is created without memory allocation—is just requires a copy of the pointer, and incrementing the reference count.

Arc<[T]>.clone()

Doesn’t perform a deepcopy. The resulting immutable reference points to the same underlying data on the heap.

Even though there’s an additional 16 bytes with the strong & weak reference counts, they are amortized with the number of clones we make. In other words, this approach is helpful if there’s a huge amount of immutable references to your underlying data.

A Youtube commented that Rc and Arc have identical runtime cost (despite cache misses from the MESI protocol, which is irrelevant in a single-threaded environment). So Rc is really only useful to semantically indicate that this data shouldn’t be shared across threads.

Double indirection with Arc<Vec<T>>

This will lead to unnecessary memory overheads from having to keep track of the Vec’s metadata (length and capacity), as well as the Arc’s strong & weak reference counts.

And getting to the underlying value likely slows down the code quite a bit due to the double address lookups.

A more efficient data structure if Clone is not needed

Footnotes

1. If not required, Box<T> is more memory-efficient, as you don’t have to spend extra memory on reference counting. See [[Arc instead of Veca-more-efficient-data-structure-if-clone-is-not-needed|A more efficient data structure if Clone is not needed]] ↩

2. This doesn’t sound like much, but it can add up if there’s a lot of references. It can also decrease cache locality, making it slower to iterate through the elements in the data structure ↩